The central question in quantum multi-prover interactive proof systems iswhether or not entanglement shared between provers affects the verificationpower of the proof system. We study for the first time positive aspects ofprior entanglement and show that entanglement is useful even for honestprovers. We show how to use shared entanglement to parallelize any multi-proverquantum interactive proof system to a one-round system with perfectcompleteness, with one extra prover. Alternatively, we can also parallelize toa three-turn system with the same number of provers, where the verifier onlybroadcasts the outcome of a coin flip. This "public-coin" property is somewhatsurprising, since in the classical case public-coin multi-prover interactiveproofs are equivalent to single prover ones.
展开▼